package digui;
import java.util.*;
public class Text {
    //题目 ： 力扣46题 全排列
    //算法 ： dfs 剪枝 + 回溯
    //全局变量
    List<List<Integer>> ret = new ArrayList<>();
    List<Integer> post = new ArrayList<>();
    boolean[] flg ;
    public List<List<Integer>> permute(int[] nums) {
        flg = new boolean[nums.length];
        dfs(nums);
        return ret;
    }

    public void dfs(int[] nums) {
        //递归出口
        if(post.size() == nums.length) {
            //添加结果
            ret.add(new ArrayList<>(post));
            return;
        }

        for(int i = 0; i < nums.length; i++) {
            if(flg[i] == false) {
                post.add(nums[i]);
                //用过了
                flg[i] = true;
                dfs(nums);
                //回溯
                flg[i] = false;
                //删掉最后那个元素
                post.remove(post.size()-1);
            }
        }
    }

    public static void main(String[] args) {

    }
}
